package com.benben.springSecurity.weiwei;

import java.util.Stack;

public class StringToTree {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x;}
    }
    //字符串转换为二叉树额思路：字符串输入的规律为root.val(root.left.val)(root.right.val)，遵循前序遍历，所以创建一个Stack来存储结点
    public  TreeNode str2tree(String s) {
        if(s == null || s.length() ==0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == ')'){
                stack.pop();
            }else if(s.charAt(i)>='0' && s.charAt(i)<='9' || s.charAt(i)=='-'){
                int start = i;
                //直到找到根元素
                while(i<s.length()-1 && s.charAt(i+1)>='0'&&s.charAt(i+1)<='9'){
                    i++;
                }
                TreeNode root = new TreeNode(Integer.valueOf(s.substring(start,i+1)));
                //获取父节点
                if(!stack.isEmpty()){
                    TreeNode parent = stack.peek();
                    if(parent.left == null){
                        parent.left = root;
                    }else{
                        parent.right = root;
                    }
                }
                //压栈
                stack.push(root);
            }
        }
        if(stack.isEmpty()){
            return null;
        }
        return stack.peek();

    }

}
